import "container/list"

/*
 * @lc app=leetcode.cn id=146 lang=golang
 *
 * [146] LRU缓存机制
 */

// @lc code=start
type LRUCache struct {
	capacity int
	list     *list.List
	m        map[int]*list.Element
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		capacity: capacity,
		list:     list.New(),
		m:        make(map[int]*list.Element),
	}
}

type Pair struct {
	k int
	v int
}

func (this *LRUCache) Get(key int) int {
	if element, ok := this.m[key]; ok {
		this.l.MoveToFront(element)
		return element.Value.(Pair).v
	} else {
		return -1
	}
}

func (this *LRUCache) Put(key int, value int) {
	//如果key已经存在，直接更新
	if element, ok := this.m[key]; ok {
		element.Value = Pair{k: key, v: value}
		this.l.MoveToFront(element)
	} else {
		if len(this.m) == capacity {
			lastElement := this.l.Back()
			key := lastElement.Value.(Pair).k
			this.l.Remove(lastElement)
			delete(this.m, k)
		}

		v := Pair{k: key, v: value}
		ptr := this.l.PushFront(v)
		this.m[key] = ptr
	}
	//如果key不存在
	//判断是否满

}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */
// @lc code=end

